class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        DP1 = [0 for _ in range(length)]
        DP2 = [0 for _ in range(length)]
        max_value = nums[0]
        for i in range(length):
            if i == 0:
                DP1[i] = nums[i]
                DP2[i] = nums[i]
            else:
                DP1[i] = max(nums[i], nums[i] * DP1[i - 1], nums[i] * DP2[i - 1])
                DP2[i] = min(nums[i], nums[i] * DP1[i - 1], nums[i] * DP2[i - 1])
                if DP2[i] > 0:
                    DP2[i] = DP1[i]
                max_value = max(max_value, DP1[i])
        return max_value


data = Solution()
nums = [2,3,-2,4]
print(data.maxProduct(nums))
nums = [-2, 0, -1]
print(data.maxProduct(nums))
nums = [1, 7, 6, 1, -5, 4]
print(data.maxProduct(nums))